For any suggestions or feedback regarding these notes,

please contact Pragy Agarwal

The 5-step design approach

(20-25 mins)

1. Problem Statement
2. Functional Requirements
3. Non-functional Requirements
4. Scale Estimation

(25-20 mins)

5. System Design

Problem Statement

“Design a messaging application”

Reason by analogy

Find existing companies / systems that offer a similar product / feature.

Gives you an overview of the umbrella of different scopes that you can consider.

• Whatsapp

• Telegram / Signal / Hike / iMessage(apple users) / Arratai
• Mobile First
• Realtime chat (ultra low latency < 3 sec for the other person to receive the message)
• built as a SMS replacement

• Slack

• MS Teams / Flock
• B2B - built for enterprise chat
• Group chat - channel(on slack) - 100k employees.

• Facebook Messenger

• Instagram Messages / Orkut messages
• Messages for social media
• 1-1 messages

What not to build

• Discord

• Voice chat - low latency.

• Orkut

• Social Media

• Twitter

• X / Threads(owned by Meta)
• Social Media

• Skype

• Facetime, Zoom
• Video Chat & Screen Sharing

• Hangouts / Google Meet

• Video Calling

• Snapchat

• Privacy -  Disappearing messages.

Functional Requirements (FR)

MVP Features

Some feature/functionality that you offer to the client (user / another internal system).

You explicitly expose an API / write code for a functional requirement.

“Who is doing what and based on that, what happens”

Actors

1. Users - (sender, receiver)
2. (enterprise software - Slack) Organisation  org ⇔ admin ⇔ HR

Whenever you think of features, think of what things the Actors can do in the app.

MVP Features

Always keep the "minimal" in your mind. MVP features is not a feature suggestion competition.

KISS: keep it simple, silly.

Practice makes perfect!

Correct practice makes perfect. Incorrect practice harms you.

Non-Functional Requirements (NFR)

Design Goals

This is additional constraints/behavior that you want your system to adhere to.

These are not “functionality” or “features” that you’re offering to the client.

Message Order

Message ordering must be maintained: the messages must be seen by the recipient in the same order as they’re sent in by the sender.

Why is message order important?

Meaning of a conversation can change based on the message order.

Idempotency

Messaging apps are typically mobile first. Mobile users don’t always get perfect internet connections. Therefore, messaging apps have to frequently deal with n/w failures.

In a lot of scenarios, the frontend app (client-side) is coded to automatically retry sending messages/posts/comments if the sending fails — because we don’t want the user to re-type the entire message.

<input id="message"

       type="text" 

       placeholder="send a message"

       onkeydown="sendMessage" />

<script>

    function sendMessage() {

        message = document.getElementById("message").text;

        sendWithRetries(message);

    }

    function sendWithRetries(message) {

        fetch("/backend-api-url/sendMessage", "POST", {

            message: message

        }).then(() => console.log("success"))

          .error(() => {

              // automatic retry after 1 second

              setTimeout(() => sendWithRetries(message), 1)

          })

    }

<script>

However, if

• the initially request successfully goes to the server
• the server acts on the request (stores the message/post/..)
• responds with an ACK
• but the acknowledgement gets lost and never reaches the user

in this case,

• the frontend will assume (incorrectly) that the server didn't receive our request
• automatically retry

due to this

• the server will end up storing the message/post again
• there will be duplicates

Automatic retries on the frontend can cause duplicates in the database!

Idempotent

A function f(x) is said to be idempotent if & only if f(x) = f(f(x))

Repeated application of the same function does nothing more than a single application.

f(x) = x2 is NOT idempotent. Because f(4) = 16, but f(f(4)) = 256.

f(x) = |x| is idempotent. Because f(-5) = 5 and f(f(-5)) = 5

Any WRITE (post/update/delete) api endpoints should be idempotent if your frontend can retry.

Q: Does the backend engineer know / care about whether the frontend guy used automatic retries?

No. They don't care.

It could be that currently the frontend doesn't retry, but later on, someone adds auto-retries to the frontend.

Therefore, irrespective of what the frontend does, we should always try to make our backend POST apis idempotent whenever possible.

Note that if the user wants to purposefully resend the same message again & again, they should be allowed to.

When I want to annoy my friends, I will send them "Hi" 20 times in a row. This should be allowed!

Duplicates due to automatic retries should be prevented.

Consistency vs Availability

PACELC

Do NOT jump to an answer

Q: What is the data ?

The messages that are being sent

Q: What does eventual consistency (stale reads) mean in this context ?

• Messages are out of order on the recipient's side
• Can't see the latest message

• Sender side

• If Pujan sends a message to Minesh at t=0
• The server ACK'd Pujan's message
• When Pujan reloaded his app at t=1, he is not able to see the message that he sent (because the read was stale)
• Pujan thinks that his message got deleted by the app
• In reality the message is not deleted/lost, if Pujan waits long enough, he will be able to see the message eventually
• This type of thing is typically solved by providing “read-your-write” consistency.

• Receiver side

• If Pujan sends a message to Minesh at t=0
• The server ACK'd Pujan's message
• At t=1 when Minesh (recipient) tries to load his messages, he isn't able to see the message that Pujan sent.

• Pujan says that he has sent the message
• But Minesh cannot receive the message
• In reality the message is not deleted/lost, if Minesh waits long enough, he will be able to see the message eventually

Q: Can we afford stale reads in this situation?

No, we cannot afford to have such stale reads.

Q: What does data loss mean in this context ?

Sender sent a message, and the server ACK'd

but, the message actually got lost by the backend.

Q: Can we afford data loss in this situation?

Very very bad. No.

Communication is the backbone of Human Society

Communication needs strong consistency!

Consistency vs Latency

What are our latency requirements?

Low Latency: < 5 seconds

We need realtime chat: if PersonA has sent a message to PersonB, and PersonB is online, then PersonB should receive the message within a few seconds.

But availability is also important!

But the PACELC theorem says that we can't have both Consistency & Latency!

Is it possible to achieve high consistency along with high availability & low latency?

No - PACELC says its impossible.

However, we can create the illusion of consistency with availability & low latency.

In reality we will give up on consistency just a little bit, but to the end user, things will still appear consistent 99.xxx% of the time

Scale Estimation

The scale will dictate our design choices

assumption: Total users = (web/planet scale) = 2 billion

Daily Active Users (DAU): 80% of all users = 1.6 billion ~= 2 billion

Typically, we consider the Pareto Principle & say that only 20% of the users will be active.

Will this be true for messaging apps like Whatsapp? No!

Instead of only 20%, for messaging apps like whatsapp, the number will be much higher

Note, for FB messenger, it might still be as low as 20%

assumption: Avg. number of messages per active-user per day

= 10 to 20 messages / active-user / day

Total number of messages / day

= (20 messages / active-user / day) * (2 billion active-users)

= 40 billion messages / day

Avg. messages / second

= 40 billion messages / day

= 4 * 1010 messages / (105 seconds)

= 4 * 105 messages / second

= 400,000 messages / second

• sendMessage(...): 400,000 per second avg
• getMessages(...):

• a message is sent once, but read multiple times
• but not by a huge margin

• in Stackoverflow/Twitter, a post is made once, and read thousands or millions of times
• in Whatsapp, a message is sent once, but read a handful of times

• assumption: = 2x of sendMessage  (each message is read twice on avg)
  = 800,000 per second
• This statistic will change for groups

• in a large group, a message is sent once, but read thousands of times
• if we have 400,000 messages/sec and each message is read 100,000 times then we have 40 billion requests/sec — this number is insane - no system (not even Google with its 10 million servers) can handle this as of 2025.
• however, in groups, the number of users participating across the globe is much lower

• slack users <<< whatsapp users
• slack only has 42 million DAU compared to whatsapp’s 2 billion.

• getConversations(...): only when the user re-opens the app

• A typical might reopen whatsapp 5-10 times per day
• 10 reopens/active-user/day  *  2 billion active users
• 20 billion reopens/day
• 200,000 requests/sec

Peak Load

assumption: = 5x of the avg load during global events like Covid or New Year

= 2 million messages / second

Total amount of data (over 20 years)

What's the data?

message: {

    sender_id: uuid (16b)

    receiver_id/group_id/conversation_id: uuid (16b)

    message_id: uuid (16b)

    text: string (200b avg)

    when: timestamp  (8b)

    where: geolocation (16b)

    delivery_status: enum (1b)

    attachment_url: string (200b avg)

}

1:1 messages - we can have a separate table

the table has a sender_id, a reciever_id, and a message

in this case our group messages table will have to be separate

group table will have sender_id, a group_id, and a message

what if we want 3 people messages. Should we create another table?

what about ah-hoc messages b/w 5 people? Another table?

NO.

Let’s merge this.

Let’s just have “conversation id”

If we’re talking about 1:1 conversations, we can just have conversation-id be a “tuple” of the (sender_id, reciever_id)

If we’re talking about group conversations, we can just use the group id as the conversation id

If we want to support ad-hoc conversations, we can have a separate table (which incorporates all scenarios – 1:1, group, 1:any)

conversation_participatns

conversation_id    user_id

Avg. size = 500 bytes/message

Amount of data / day

= (500 bytes / message) * (40 billion messages / day)

= 20 trillion bytes / day

= 20 TB / day

Amount of data over 20 years

= (20 TB / day) * (20 years)

= (20 TB / day) * (20 * 365 days)

= (20 TB / day) * (~ 10,000 days)

= 200 Petabytes

Can this amount of data fit on a single server?

No. As of 2026, we can store up to 3 PB on a single server, not 200PB. Even if we could, a single server won’t be able to handle 2 million messages/sec.

We definitely need sharding!

Read Heavy vs Write Heavy?

Writes (sendMessage): 400,000 / second (avg)  2 million/sec (peak)

Reads (getMessages): 800,000 / second (avg)  4 million/sec (peak)

Neither is 10x or more larger than the other - neither is dominating.

This is both read & write heavy, but neither dominates!

It is very challenging to design systems which are both read & write heavy.

This means that we will either have to convert this into a read heavy system or into a write heavy system.

Can we reduce the writes (batching/sampling)? No.

So the only solution is to reduce the reads that go to the database — by absorbing the reads in the cache. Also, since the messages are mostly immutable (edits/deletes are rare), caching will work well.

So we will have lots of cache, and the database will be optimized for writes.

System Design
Idempotency & Message Order

Each message will have a unique message id that is generated on the client side

1. UUID v7

• universally unique, decentralized, sparse, roughly sortable
• widely accepted spec
• popular implementations in every major language
• 128 bit
• high performance

Idempotency

• whenever the backend receives a sendMessage API call, it stores the message in the DB only if the message_id is not already there in the DB
• if the message_id is already there in the DB, it will just ignore the request, but, it will still send a success response (so the frontend can stop retrying)

<input id="message"

       type="text" 

       placeholder="send a message"

       onkeydown="sendMessage" />

<script>

     function sendMessage() {

          var content = document.getElementById("message").text;

          var message = {

              id: uuid_v7(), // note that this id will

                             // remain unchanged for the retries

              content: content,

              timestamp: new Date(),

          }

          sendWithRetries(message);

      }

      function sendWithRetries(message) {

          fetch("/backend-api-url/messages", "POST", {

              message: message

          }).then(() => console.log("success"))

            .error(() => {

                // automatic retry after 1 second

                setTimeout(() => sendWithRetries(message),

                           1)

          })

        }

<script>

Message Order

1. Sorting based on created_time timestamp will NOTwork

• because the recipient doesn't even know that there's a message pending until the message arrives
• by the time the receiver's app realises that an intermediate message arrived late, it was already too late - it had already shown the later messages to the user

2. note that no backend based solution (SQS/buffer/...) will work

• because the backend doesn't even know that there's a message pending until the message arrives
• by the time the server realises that an intermediate message arrived late, it was already too late - it had already put later messages in the queue

Solution: create a message chain

Every new message should contain the previous_message_id inside it.

On the recipient's side, the app will not show a message unless its previous message has also been received & shown.

Instead, if a message appears out-of-order, it will show waiting-for-messages until all the previous messages have arrived.

<input id="message"

       type="text" 

       placeholder="send a message"

       onkeydown="sendMessage" />

<script>

     var previous_id = null;

     function sendMessage() {

          var content = document.getElementById("message");

          var id = uuid_v4()

          var message = {

              previous_id,     // id of last message that I sent

              id: id,

              content: content,

              timestamp: new Date(),

          }

          previous_id = id;

          sendWithRetries(message);

      }

<script>

Q: What happens when there are multiple devices, or, multiple people sending messages in the same chat (group chat maybe) concurrently. In this case, how do we maintain the previous-message-id?

Don’t worry. We’re not guaranteeing any sort of message order across multiple senders.

The intent of maintaining message order is to ensure that all messages sent by “Subhadeep” appear in the correct order. Messages sent by multiple senders can be interleaved in any way - we don’t care, as long as the messages of each individual sender are in the correct order!

Sharding

Sharding Key: user_id

This means that all the data (messages send & received) of a particular user will be within the same shard.

Q: Does sharding by user_id mean that if we have 2 billion users, we need 2 billion servers?

No! A single server will hold the data for hundreds of thousands of users.

1-1 messages

getMessages(user_id, conversation_id, ...)

Only go to the user's shard, because all messages sent/received by the user will be present in their shard.

sendMessage(sender_id, receiver_id, ...)

Go to both sender & receiver's shard (data replication)

recentConversations(user_id)

Only go to the user's shard

Group Messages

getMessages(user_id, group_id, ...)

1. Store in Sender Only: Reads will be fan-out
   because messages sent by different senders in the same group will be stored in different shard
2. Store in All Participants: fast reads, because we can read from any shard

sendMessage(sender_id, group_id, ...)

1. Store in Sender Only: Store it only in the sender's shard
2. Store in All Participants’ shards: Fan-out writes

recentConversations(...)

Basically, sharding by user_id will NOT work for group conversations.

Either reads will be fan-out, or writes will be fan-out.

Sharding Key: conversation_id

For groups, conversation_id = group_id

For 1-1 chats, conversation_id = unique id assigned to a pair of users

1-1 messages

getMessages(user_id, conversation_id, ...)

Only go to the conversation's shard, because all messages sent/received by the any participant of that conversation will be present in that shard.

sendMessage(sender_id, receiver_id, ...)

Go to  conversation's  shard

What’s the conversation id? It’s just the pair (sender_id, receiver_id)

recentConversations(user_id)

Will be fan-out => bad

We can have a separate db to store the most recent conversations.

Note that now, the sendMessage must also update the recentConversations DB.

Note: the recentConversations DB holds information (last message timestamp) about all conversations.

It doesn't only store recentConversations.

It's called the recentConversations DB because we're using it to answer the recentConversations(...) query exclusively.

Group Messages

Note that a group is just a conversation amongst a lot of people.

getMessages(user_id, group_id, ...)

just go to the group's shard

sendMessage(sender_id, group_id, ...)

just store in the group's shard

recentConversations(user_id)

No matter what you do, the moment a message is sent in a group, the most recent conversation gets updated for potentially 100,000 users!

This will always be a fan-out no matter what you do.

Therefore, you will not provision this API for group conversations.

Practically: happens only at frontend.

Client side app can maintain a cache of recent conversations.

This cache data is updated thanks to notifications.

users (id, name, age, avatar_url)

conversations (id, title, description)

conversation_participants (conversation_id, user_id)

messages (id, sender_id, conversation_id, message)

What to choose?

• Facebook Messenger / Whatsapp: Group size is limited - sharding by user_id is ideal
  
• Slack / MS Teams: Groups are a core feature, and groups can potentially get very large (100,000+ users) - sharding by conversation_id is ideal

Consistency

PACELC: Consistency vs Availability/Latency

PACELC says if we want consistency, we have to give up on availability & latency.

We do want consistency.

Assume that we're sharding by user_id. In this case, any write must go to 2 shards - sender & receiver.

And we must maintain consistency during this write.

Option 1: use 2 Phase Commit (2PC) to write to both shards atomically

• extremely slow (low throughput & high latency)
• low availability

Can we instead create an illusion of consistency?

Instead of trying to write atomically, let's try to write 1 by 1.

Write to Sender shard first

Riya  – bro can I copy your project submission? → Aditya

(sender)                                            (recipient)

• Write the message to Sender's shard

• Failure (low latency)

• immediately return a failure & we’re done!

• client can retry to send the message

• Success

• At this point, can we return “success” to the sender?

• No! Because the data has not been written to the receiver shard yet
• This means that if the receiver tries to getMessages, then they will not be able to see this message, even though, the sender believes that the message has been sent.
• Inconsistency

• Sender: bro, I sent it
• Receiver: bro, you didn’t!

• Write to the Receiver's shard

• Success (low latency)

• immediately return a success
  (we've successfully written to both sender & receiver's shard)

• Failure (high latency)

• the data is in an inconsistent state (written to sender shard, but not to receiver shard)
• right now, the sender thinks that the message has been sent, but if the recipient tries to load their messages, they don't see this message

• this is extremely bad.

• Retry

• the sender has to wait until the retry succeeds
• very high latency, because the sender has to wait until the retry finally succeeds

• Rollback

• we can return an error
• but now, the system is in an inconsistent state until the rollback completes.

• so we cannot let the sender make any reads until the rollback completes – we’ve acquire locks
• this means that reads for the sender will have high latency

Write to Receiver shard first

• Write to the Recipient's shard

• Failure (low latency)

• Immediately return a failure

• Client (sender) can retry

• Success

• the message has actually been sent!
  At this point, if the recipient fetch their messages, they will be able to see this new message
• Immediately return a success
  (without even writing to sender shard)
  very low latency
• (async) Write to the Sender's shard

• Success

• great, we're done

• Fails

• just keep retrying until it succeeds
• the sender isn't waiting, they're already received an acknowledgement
• so no added latency here

Note that if the initial write to Recipient's shard succeeds, but the initial write to Sender's shard fails - when the sender tries to reload their app, they will not be able to see the message that they just sent.

This means that the sender thinks that their message has been deleted ⇒ bad!

We can fix this by simply having a frontend cache (cache inside the client app)

The app will know what messages have been sent. Even though the getMessages API doesn't show this message, the frontend app will know that this message was sent and acknowledged by the server.

The only situation when this will be an issue will be when the sender sends a message, the sender's shard is misbehaving in the backend, the sender reinstalls their frontend app (or clear the app cache), and then they try to see the message.

This is v.v. rare, so not an issue.

Note that the message has NOT been lost. Eventually the sender shard will come back up, and the message will be replicated there from the receiver shard.

By cleverly writing to recipient's shard first, and utilizing the frontend cache at the sender side, we can create an illusion of immediate consistency.

It solves the practical problem for us.

Consistency vs Availability

Imagine that there's a partition.

Harini  ----- "Hi" -----> Srinidhi

App Server 1 receives this request.

App server 1 is able to communicate with Srinidhi's Shard, but because of a n/w partition, it is not able to communicate with Harini's Shard.

App server will just write to Srinidhi's shard (recipient), and return success to Harini.

It will also drop a message in a task queue to add this message to Harini's shard in an async manner.

Even in case of n/w partition, the sendMessages & getMessages remains available => High Availability

Srinidhi can see the message because it is written to her shard. And because of the frontend cache, Harini can also see the message. => (illusion) Immediate Consistency

Note: if the write to Srinidhi's shard fails, then we can return an error to Harini & then they can retry.

Consistency vs Latency

Because we're not actually trying to write to both shards in an atomic manner, we don't have to wait for retry/rollback to complete.

We can just return success the moment we write to recipient shard.

Low Latency

Choosing the right Database

Writes (sendMessage): 400,000 / second avg (peak: 2 million / sec)

Reads (getMessages): 800,000 / second avg (peak: 4 million / sec)

Both Read & Write Heavy!

No database is optimized for both reads & writes!

Optimizing Reads/Writes

Can we optimize writes?

One can optimize writes by either batching or sampling

• Batching: causes stale reads
  but we want low latency
• Sampling: causes potential data loss
  we cannot afford data loss

Can we optimize reads?

Just try to absorb as many reads as possible via a cache.

Now that we're absorbing the majority of reads in the cache, we can optimize our database for writes!

Ideal Database

Requirements

1. High write throughput (400,000 writes/sec avg)
2. No need of joins

1. No: find all messages of all friends of Akshay
2. Yes: find all messages of Akshay (filter: within a conversation)

3. No need of search (if we need it later, we can provision another database in a separate microservice)
4. Paginated reads (by timestamp)
5. No need of transactions
6. We want disk persistence

SQL

Strengths: ACID transactions, normalizations, joins, schema

Weaknesses: low throughput, can’t scale horizontally

Key-Value

Strengths: High throughput, simplicity

Weaknesses: No search, No joins, No pagination

We need pagination!

Document

Strengths: Schemaless, search, (local) index on any attribute

Weaknesses: No joins, No pagination, …

We do need pagination. We don’t need search

Column-Family db

Strengths: Fast writes, Time based pagination, Fast aggregate queries

Weaknesses: No joins, no search, ..

This is exactly what we need!

Ideal database is therefore a Wide Column Database - HBase / Cassandra / ScyllaDB.

Cache

5 step process to cache design

1. Establish the need for caching
2. Determine the type of cache

1. Local vs Global
2. Single vs Distributed   (only if global cache)

3. Identify the Invalidation algorithm based on

1. consistency requirements
2. data/query complexity

4. Identify the Eviction algorithm

1. just use LRU

5. Think about the load balancer (consistent hashing vs round robin)

Local vs Global (Single) vs Global (Distributed)

• Should we go with a Single, global cache?
  No! We needs lots of cache, so we need something distributed (local/global)
  
• Do we need to transfer lots of data b/w app server & cache server to handle a read request? Is the n/w overhead going to be an issue for every call?
  (getMessages(user_id, conversation_id, pagination))
  No. In given call, I’m only reading a few messages. Low n/w overhead.
  
• We should probably think of a Global Cache

• Will a single cache server be able to handle all the data?
  No.
• We're looking at a distributed global cache

• But in this case, what is the app server for the getMessages API doing?
  Nothing - just passing the request forward to the cache server
• If we go with a global cache, we now have 2x the twice the number of servers (app servers + cache servers), and half of them are not doing anything!
• If we go with a global cache, getting read-your-write consistency will be hard! In a local cache it will be very simple (because local writes will succeed)

So instead of having a global cache and then having useless app servers, we can simply use a local cache.

App servers now double as the cache.

Invalidation

We want immediate consistency, but we don't want the latency that comes with immediate consistency.

• If we have a separate app server & cache server, immediate consistency requires 2 phase commit, because we've to keep the cache & db up to date (2 places)
• If we have local cache, then writing to the cache is always successful. No need of 2PC here.

Because of the local cache, we can get write-through invalidation (immediate consistency) without high latency.

Eviction

LRU eviction

Routing

Our app servers are stateful. If an app servers holds Harini's messages in cache, we want Harini's requests to always go to that app server.

Consistent Hashing.

getMessages(user_id, conversation_id) ⇒ this request just goes to my shard & to my app-server+cache, because all my messages are contained there

sendMessages(sender_id, recipient_id) ⇒ this request will be routed to recipient shard & app-server+cache first (via the routing) and the data will be written there. (Async) via a message queue, we will replicate this data in the sender shard & app-server+cache.

messages

id   sender_id   recipient_id   message

1      Jinesh         Anika                  Hi

When we say that we’re sharding by user_id, what does this mean? How do we shard this table by user_id, when it doesn’t even have a user_id column?

row_id    user_id         id   sender_id   recipient_id   message

123             Jinesh       1      Jinesh         Anika                  Hi        

                                                          → this will go to only Jinesh’s shard

321             Anika                 1      Jinesh        Anika                 Hi

Now if we shard by user_id, then

Jinesh’s shard

row_id    user_id         id   sender_id   recipient_id   message

123             Jinesh       1      Jinesh         Anika                  Hi

Anika’s shard

row_id    user_id         id   sender_id   recipient_id   message

321             Anika                 1      Jinesh        Anika                 Hi

What happens if a cache server crashes?

The users originally going to this server have to be redirected to another server. This other server doesn't have their messages cached.

Cold cache problem - data not in cache, fetch it from DB

Some of the time (when the cache server crashes), some of the users (only those that were originally going to the now crashed server), will see a larger latency for first few reads. That is perfectly okay.